import java.util.*;
/**
 * @author LKQ
 * @date 2022/4/27 23:17
 * @description 任意两点之间的最短路可以通过枚举起点，跑 n 次 BellmanFord算法实现，时间复杂度为 O(n^2· m)
 * 由于 Dijkstra算法时间复杂度为 O(M * logM) 因此若使用此算法代替 BellmanFord， 跑 n 次，那么总时间复杂度为 O(N*M*logM)
 * 在稀疏图上比Floyd算法的时间复杂度也更加优秀。但由于Dijkstra算法不能处理负权图，因此，需要先跑一次 BellmanFord 对原图上的边预处理。
 */
public class Solution {

    /**
     * 存储图
     */
    List<int[]>[] graph;
    /**
     * 存储任意两点之间的最短路
     */
    int[][] dis;
    /**
     * 正无穷
     */
    int INF = Integer.MAX_VALUE / 2;


    /**
     * Johnson算法。
     * @param n n个结点，由于需要使用虚拟结点，我们将 原图中点结点编号为 1 - n，虚拟结点 设定 为 0
     * @param edges e[0] 到 e[1] 的权值 为 e[2]
     */
    public void Johnson(int n, int[][] edges) {
        // 1. 根据edges 建图
        graph = new List[n + 1];
        for (int i = 0; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] e: edges) {
            // 如果edges中，结点编号从1到n，那么直接赋值, 若结点编号 从 0到 n-1, 那么结点编号加一再赋值
            // graph[e[0] + 1].add(new int[] {e[1] + 1, e[2]})
            graph[e[0]].add(new int[]{e[1], e[2]});
        }
        // 2. 初始化dis数组
        dis = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            Arrays.fill(dis[i], INF);
            dis[i][i] = 0;
        }

        // 3. 建立虚拟结点0，0到其他结点的权值为 0
        graph[0] = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            graph[0].add(new int[] {i, 0});
        }

        // 4. 跑一次 BellmanFord算法，求出虚拟结点到其他点的最短路，记为 h(u)
        int[] h = BellmanFord(n, graph);
        System.out.println("虚拟结点 0 到其他结点的最短路为 " + Arrays.toString(h));

        if (h != null) {
            // 5. 将原图中边的权值重新设置为 w + h(u) - h(v)
            for (int u = 1; u <= n; u++) {
                for (int[] e: graph[u]) {
                    int v = e[0], w = e[1];
                    e[1] = w + h[u] - h[v];
                }
            }
            // 6. 以每个结点为起点，跑 n 轮 Dijkstra算法。
            for (int u = 1; u <= n; u++) {
                dis[u] = Dijkstra(n, u, graph);
                // 注意，最后的最短路径还需要加上 h(v) - h(u)，才能得出原来的最短路径长度
                for (int v = 1; v <= n; v++) {
                    if (v != u) {
                        dis[u][v] += h[v] -h[u];
                    }
                }
                System.out.println("结点" + u + " -> other points " + print(dis[u]));
            }
        }else {
            // 返回了 null, 说明虚拟结点到其他结点的最短路不存在，说明原图中存在负环。
            System.out.println("图中存在负环，");
        }
    }
    public int[] BellmanFord(int n, List<int[]>[] graph) {
        // 初始化虚拟结点0 到其他结点的最短路
        int[] dis = new int[n + 1];
        Arrays.fill(dis, INF);
        dis[0] = 0;

        // 设置flag 标志，判断一轮循环过程中是否发生松弛
        boolean flag = false;

        // 4. bellman-Ford
        for (int i = 0; i < n; i++) {
            flag = false;
            for (int u = 0; u < n; u++) {
                // 无穷大与常数加减仍然为无穷大
                // 因此最短路长度为 inf 的点引出的边不可能发生松弛操作
                if (dis[u] == INF) {
                    continue;
                }
                for (int[] e: graph[u]) {
                    int v = e[0], w = e[1];
                    if (dis[u] + w < dis[v]) {
                        dis[v] = dis[u] + w;
                        flag = true;
                    }
                }
            }
            // 没有可以松弛的边就停止算法
            if (!flag) {
                break;
            }
        }
        // 第 n 轮循环仍然可以松弛说明s点可以抵达一个负环，那么返回 null, 否则返回 最短路数组dis
        return flag ? null : dis;
    }

    public int[] Dijkstra(int n, int s, List<int[]>[] graph) {
        // n个结点，编号 1-n
        int[] dis = new int[n + 1];
        Arrays.fill(dis, INF);
        // 源点到自身的距离为0
        dis[s] = 0;

        // 初始化访问标志，默认为false
        boolean[] vis = new boolean[n + 1];

        // 使用优先队列维护最短路径中最短路最小的点，优化时间
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)-> a[1] - b[1]);
        pq.add(new int[]{s, 0});

        while (!pq.isEmpty()) {
            // 弹出最短路长度最小的点数组
            int[] t = pq.poll();
            int u = t[0];
            // 该点访问过，跳过
            if (vis[u]) {
                continue;
            }
            vis[u] = true;
            // 遍历所以 u 能够到达的点
            for (int[] q: graph[u]) {
                // 下一个点 v, 即其边权值 w
                int v = q[0], w = q[1];
                if (dis[v] > dis[u] + w) {
                    // s->v 的距离 > s->u 的距离 + u->v 的距离，更新最短距离
                    dis[v] = dis[u] + w;
                    // 加入优先队列，s->v 的距离 dis[v]
                    pq.add(new int[]{v, dis[v]});
                }
            }
        }
        return dis;
    }

    public String print(int[] dis) {
        StringBuffer sb = new StringBuffer();
        sb.append("[");
        for (int a: dis) {
            if (a > INF / 2) {
                sb.append("INF, ");
            }else {
                sb.append(a + ", ");
            }
        }
        sb.replace(sb.length() - 2, sb.length(), "");
        sb.append("]");
        return sb.toString();
    }

    public static void main(String[] args) {
        int[][] edges = {{1, 4, 2}, {4, 2, -3}, {1, 5, 0}, {5, 3, 2}, {3, 2, -4}};
        Solution solution = new Solution();
        solution.Johnson(5, edges);
    }
}
